lib/Documentation/9thinksYouNeed-ACMSolver/sieve by yarin.cpp

   1 // Super fast & Memory-tight Sieve by Yarin
   2
   3 #include<stdio.h>
   4 #include<stdlib.h>
   5 #include<string.h>
   6
   7 #define MAXSIEVE 100000000 // All prime numbers up to this
   8 #define MAXSIEVEHALF (MAXSIEVE/2)
   9 #define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
  10 char a[MAXSIEVE/16+2];
  11 #define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
  12
  13 //have to check for even numbers
  14 void sieve()
  15 {
  16         int i,j;
  17         memset(a,255,sizeof(a));
  18         a[0]=0xFE;
  19         for(i=1;i<MAXSQRT;i++)
  20                 if (a[i>>3]&(1<<(i&7)))
  21                         for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
  22                                 a[j>>3]&=~(1<<(j&7));
  23 }